# 第3节Bellman-Ford———解决负权边
# 因为最短路径是一个不包含回路的简单路径，回路分为正权回路(回路权值之和为正)和负权回路(回路权值之和为负)。
# 如果最短路径中包含正权回路，那么去掉这个回路，一定可以得到更短的路径；如果最短路径中包含负权回路，那么
# 肯定没有最短路径，因为每多走一次负权回路就可以得到更短的路径. 因此最短路径肯定是一个不包含回路的最短路
# 径，即最多包含n-1条边。
a = [[0, 0, 0, 0],
     [0, 2, 3, 2],
     [0, 1, 2, -3],
     [0, 1, 5, 5],
     [0, 4, 5, 2],
     [0, 3, 4, 3]
     ]
n = 5  # 顶点个数
m = 5  # 边个数
dis = [99 for i in range(0, n + 1)]
dis[1] = 0
# Bellman-ford算法核心语句
for k in range(1, n):
    for i in range(1, m + 1):
        u = a[i][1]
        v = a[i][2]
        w = a[i][3]
        if dis[v] > dis[u] + w:
            dis[v] = dis[u] + w
# 检测负权回路
flag = 0
for i in range(1, m + 1):
    u = a[i][1]
    v = a[i][2]
    w = a[i][3]
    if dis[v] > dis[u] + w:
        flag = 1
print(dis)
if flag == 1:
    print('有负权回路')
